//
// Created by 紫霄 on 2020/4/28.
//

#ifndef LEETCODE_59_1_H
#define LEETCODE_59_1_H
#include <deque>
#include <vector>
using namespace std;
// class Solution {
// public:
//  vector<int> maxSlidingWindow(vector<int> &nums, int k) {
//    int sz = nums.size();
//    if (sz <= 1) {
//      return nums;
//    }
//    int nowMax = nums[0];
//    for (int i = 0; i < k; ++i) {
//      if (nums[i] > nowMax) {
//        nowMax = nums[i];
//      }
//    }
//    vector<int> ans;
//    ans.emplace_back(nowMax);
//    for (int i = 1; i < sz - k + 1; ++i) {
//      if (nums[i + k - 1] > nowMax) {
//        nowMax = nums[i + k - 1];
//      } else if (nums[i - 1] == nowMax) {
//        nowMax = nums[i];
//        for (int j = i; j < i + k; ++j) {
//          if (nums[j] > nowMax) {
//            nowMax = nums[j];
//          }
//        }
//      }
//      ans.emplace_back(nowMax);
//    }
//    return ans;
//  }
//};

//// 使用deque实现；

class Solution {
public:
  vector<int> maxSlidingWindow(vector<int> &nums, int k) {
    if (nums.size() < 2) {
      return nums;
    }
    deque<int> temp;
    vector<int> ans;
    for (int i = 0; i < k; ++i) {
      while (!temp.empty() && nums[i] > nums[temp.back()]) {
        temp.pop_back();
      }
      temp.emplace_back(i);
    }
    ans.emplace_back(nums[temp.front()]);
    for (int i = 1; i < nums.size() - k + 1; ++i) {
      // nums[i+k-1]是以nums[i]为开头的末元素
      while (!temp.empty() && nums[i + k - 1] > nums[temp.back()]) {
        temp.pop_back();
      }
      if (!temp.empty() && temp.front() < i) {
        temp.pop_front();
      }
      temp.emplace_back(i + k - 1);
      ans.emplace_back(nums[temp.front()]);
    }
    return ans;
  }
};
#endif // LEETCODE_59_1_H
